package com.example.algorithm.no0042.solution;

import com.example.algorithm.no0042.Solution;

/**
 * @Description 两数之和-for循环遍历
 * 时间复杂度：O(n^2)
 * 对于每个元素，我们试图通过遍历数组的其余部分来寻找它所对应的目标元素，这将耗费 O(n)O(n) 的时间。因此时间复杂度为 O(n^2)。
 * 空间复杂度：O(1)
 * @ClassName SumTwoNum
 * @Author Administrator
 * @Date 2020/5/16 12:48
 * @Version 1.0.0
 */
public class DpSolution implements Solution {

    /**
     * {0,1,0,2,1,0,1,3,2,1,2,1}   6
     *
     * @param height {0,1,0,2,1,0,1,3,2,1,2,1}
     */
    @Override
    public int trap(int[] height) {

        if (height == null || height.length == 0) {
            return 0;
        }

        int size = height.length;

        int[] leftMax = new int[size];
        int[] rightMax = new int[size];

        leftMax[0] = height[0];
        for (int i = 1; i < size; i++) {
            leftMax[i] = Math.max(leftMax[i - 1], height[i]);
        }

        rightMax[size - 1] = height[size - 1];
        for (int i = size - 2; i >= 0 ; i--) {
            rightMax[i] = Math.max(rightMax[i + 1], height[i]);
        }

        int res = 0;
        for (int i = 1; i < size - 1; i++) {
            res += Math.min(leftMax[i], rightMax[i]) - height[i];
        }

        return res;
    }
}
